//
//  Letcode.swift
//  SFQuestion
//
//  Created by sr liu on 2021/8/4.
//

import Foundation

//letcode上的题  一般是看博客遇到的讲解

class LetCode {
    //MARK:-62 机器人不同路径 动态规划
    //m*n的网格，从左上角走到右下角
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        //m行 n列
        if m <= 0 || n <= 0 {
            return 0
        }
        var dp = [[Int]].init(repeating: ([Int].init(repeating: 0, count: n)), count: m)
        for i in 0..<m {
            dp[i][0] = 1
        }
        for i in 0..<n {
            dp[0][i] = 1
        }
        for i in 1..<m {
            for j in 1..<n {
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            }
        }
        let road = dp[m-1][n-1]
        
        return road
    }
    
    /*
     思考优化：从循环体入手加画图
     每一次循环其实是在每一行按顺序求值，所以只需保留上一行内容和左边内容，并不断更新那一行数组即可。那么为了更省空间  我们看m和n谁小，m小按列求值，n小按行求值。
     但是 不管m行 n列 还是m列n行 最终结果都不变
     */
    func uniquePaths1(_ m: Int, _ n: Int) -> Int {
        //m行 n列
        if m <= 0 || n <= 0 {
            return 0
        }
        var row = m
        var column = n
        
        if m < n {
            row = n
            column = m
        }
        //注意初始值
        var dp = [Int].init(repeating: 1, count: column)
        
        for _ in 1..<row {
            dp[0] = 1//每一行第一列是1
            for j in 1..<column {
                dp[j] = dp[j - 1] + dp[j]
            }
        }
        return dp[column - 1]
    }
    
    //MARK:-64 机器人最小路径和 动态规划
    /*
     这个相当于初值不是1
     分各种边界情况，
     1、旧办法创建一个二维数组,注意顶角  左右边界 初始赋值 和 累加即可
     2、可以优化到O(n) min(m,n)我目前想到的办法是通过判断写不同的循环 就是先行后列 或 先列后行，因为不能随意交换了。不知道鬼对不对，就先不优化到min（m,n）
     3、由于二维数组用完了之后左上角的其实没有用了，可以直接在原数组修改。但是swift不是inout参数，先忽略这个解法
     */
    func minPathSum(_ grid: [[Int]]) -> Int {
        let m = grid.count//行
        var n = 0//列
        
        for inArr in grid {
            n = inArr.count
            break
        }
        
        if m <= 0 || n <= 0 {
            return 0
        }
        
        var dp = [Int].init(repeating: 0, count: n)
        var temp = 0
        for (index, item) in grid[0].enumerated() {
            dp[index] = temp + item
            temp = dp[index]
        }
        
        for i in 1..<m {
            dp[0] = grid[i][0] + dp[0]
            for j in 1..<n {
                if j < grid[i].count {//判断下越界
                    dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
                }
                
            }
        }
        return dp[n-1]
    }
    
    
    //MARK:-415、字符串相加
    func addStrings(_ num1: String, _ num2: String) -> String {
        if num1.count == 0 {
            return num2
        } else if (num2.count == 0) {
            return num1
        }
        var str = ""
        var p1 = num1.count - 1
        var p2 = num2.count - 1
        var takeOver = false
        while p1 >= 0 || p2 >= 0 {
            var sum = sumStr(num1, p1, num2, p2)
            if takeOver {
                sum = sum + 1
            }
            if sum / 10 == 1 {
                takeOver = true
            } else {
                takeOver = false
            }
            let one = sum % 10
            str = String.init(one) + str//新生成的拼接在前面
            
            (p1 > 0) ? (p1 -= 1) : (p1 = -1)
            (p2 > 0) ? (p2 -= 1) : (p2 = -1)
        }
        
        if takeOver {
            str = "1" + str
        }
        
        return str
    }
    
    func sumStr(_ a: String, _ p1: Int, _ b: String, _ p2: Int) -> Int {
        var sum = 0
        var s1: Character = "0"
        var s2: Character = "0"
        if p1 >= 0 {
            s1 = a[a.index(a.startIndex, offsetBy: p1)]
        }
        if p2 >= 0 {
            s2 = b[b.index(b.startIndex, offsetBy: p2)]
        }
        sum = (Int(s1.asciiValue!) - 48) + (Int(s2.asciiValue!) - 48)
        return sum
        
    }
    
    
    //1143. 最长公共子序列
    func longestCommonSubsequence(_ text1: String, _ text2: String) -> Int {
        var len = 0
        let len1 = text1.count
        let len2 = text2.count
        var dp = Array(repeating: Array(repeating: 0, count: len2+1), count: len1+1)
        let startIndex1 = text1.startIndex
        let startIndex2 = text2.startIndex
        for i in 1...len1 {
            let c1 = text1[text1.index(startIndex1, offsetBy: i - 1)]
            for j in 1...len2 {
                let c2 = text2[text2.index(startIndex2, offsetBy: j - 1)]
                if c1 == c2 {
                    dp[i][j] = dp[i-1][j-1] + 1
                } else {
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
                }
            }
        }
        len = dp[len1][len2]
        return len
    }
    
}



/**
 * Your LRUCache object will be instantiated and called as such:
 * let obj = LRUCache(capacity)
 * let ret_1: Int = obj.get(key)
 * obj.put(key, value)
 */
class LRUCache {
    
    var capacity = 0
    var size = 0
    var map = [Int: CacheNode]()
    var head: CacheNode?//
    var tail: CacheNode?

    init(_ capacity: Int) {
        self.capacity = capacity
    }
    
    func get(_ key: Int) -> Int {
        if let node = map[key], let value = node.value {
            self.moveToHead(node)
            return value
        }
        return -1
    }
    
    func put(_ key: Int, _ value: Int) {
        if let node = map[key] {
            node.value = value
            self.moveToHead(node)
            return;
        }
        if size > 0 && size >= capacity {
            self.removeTail()
            size -= 1
        }
        let newNode = CacheNode(key: key, value: value)
        map[key] = newNode
        
        if let _ = head {
            self.insert(newNode)
        } else {
            head = newNode
            tail = newNode
        }
        size += 1
        
    }
    
    func insert(_ node: CacheNode) {
        node.next = head
        head?.pre = node
        head = node
    }
    
    func moveToHead(_ node: CacheNode) {
        
        //得判断头尾，保证不断，不错指
        if let h = head, h.key == node.key {
            return
        }
        
        if let t = tail, t.key == node.key {
            t.pre?.next = nil
            tail = t.pre
        } else {
            node.pre?.next = node.next
            node.next?.pre = node.pre
        }
        node.next = head
        node.pre = nil
        head?.pre = node
        head = node
        
    }
    
    func removeTail() {
        if let t = tail, let key = t.key {
            map.removeValue(forKey: key)
            
            if let h = head, h.key == key {
                head = nil
                tail = nil
            }
            tail = t.pre
            tail?.next = nil
        }
    }
        
}

class CacheNode {
    var pre: CacheNode?
    var next: CacheNode?
    var key: Int?
    var value: Int?
    init(key: Int, value: Int) {
        self.key = key
        self.value = value
    }
}

